S-DESの暗号化をRustで実装してみた

S-DESの暗号化をRustで実装してみた

情報処理安全確保支援士の勉強とRustの勉強を兼ねてやってみました。
Clock Icon2024.09.24

こんちは、リテールアプリ共創部のmorimorikochanです。

情報処理安全確保支援士の勉強で様々な暗号について勉強していたのですが、DES・AESの処理フローや暗号利用モードのイメージがつかずいまいち頭に定着しませんでした。

最近Rustを書いていなくRustの肩慣らしの意味も込めて、Rustで1からS-DESを実装してみました。

S-DESとは

S-DESとは、共通鍵暗号の一種でDES(Data Encryption Standard)が簡略化(Simplified)されています。
主に教育目的で使用されることを目的に作られました。そのため実務で利用されることはおすすめされていません(DES自体も今は非推奨となっていますが)

また、S-DESはブロック暗号であり、ブロックのサイズは8bit、鍵長は10bitとなっており、AESや通常のDESと比べとても小さく扱いやすくなっています。

自分でスクラッチで実装するには良さそうですね

DESとS-DESの共通点

DESではざっくりですが以下のような処理を行います。

DESのFeistel構造全体 DESの鍵スケジュール
500px-DES-main-network DES-key-schedule

https://ja.wikipedia.org/wiki/Data_Encryption_Standard#全体構造

後述のS-DESと比較すると以下の点が一致しており、S-DESはFeistel関数やラウンド数などがDESと比べて簡略化されていることがわかります。

  • Initial Permutation(IP)を行い、
  • Feistel関数を複数回(ラウンド数分)実行し
  • Final Permutation(FP)を行う
  • 1つの鍵からラウンドごとに鍵(SubKey)を生成する

S-DESの暗号化の仕組み

S-DESの暗号化の流れを図でまとめてみました。大枠の処理フローは左側に記載の通りです。
また、右側にはFeistel関数の処理について掘り下げて記載しています。
以下、特筆すべき処理を取り上げて簡単に説明していきます。

sdes (2)

Initial Permutation(IP)

ここでは、入力された8bitを並べ替えて出力します。

ip (1)

たとえば、先頭のbit列b1は4番目に移動、2番目のbit列b2は1番目に移動... という感じになります。
入力が0b10010111の場合は出力は0b01011101になります。

Feistel関数

ここでは、IP実行後の8bitとSubKey(8bit)を入力として、8bitを出力します。

Expanded Permutation(EP)

Feistel関数内で実行される処理です。入力された4bitを8bitに増幅します。

ep

S-box

Feistel関数内で実行される処理です。ざっくり以下の処理を行います。

  • 1bit目と4bit目から行を計算
  • 2bit目と3bit目から列を計算
  • S-boxの値を出力

これについては実際にコードを見た方が早いと思います。

fn sbox(data: u8) -> u8 {
  let sbox0: [[u8; 4]; 4] = [
    [1, 0, 3, 2],
    [3, 2, 1, 0],
    [0, 2, 1, 3],
    [3, 1, 3, 2]
  ];
  let row = ((data & (1 << 3)) >> 2) | (data & 1);
  let column = ((data & (1 << 2)) >> 1) | ((data & (1 << 1)) >> 1);
  return sbox0[row as usize][column as usize];
}

冒頭で定義されているS-boxは2種類存在しています。そのためそれぞれで異なる出力がされます。

Permutation P4

Feistel関数内で実行される処理です。入力された4bitを並べ替えて4bitを出力します。

p4 (1)

Final Permutation(FP)

最後にFinal permutation(FP)を行います。これは前述のInitial Permutation(IP)と逆に並べ替えます。

たとえば、先頭のbit列は2番目に移動、2番目のbit列は6番目に移動... という感じになります。

fp

Rustで実装してみた

ソースコードの暗号化処理のみ抜粋
use std::fs;

fn main() {
    let (key1, key2) = generate_key(0b1010000010);

    let plain_text = fs::read("./plain.txt").unwrap();

    let encrypted_text = plain_text
        .iter()
        .map(|char| encrypt(char.clone(), key1, key2))
        .collect::<Vec<_>>();

    fs::write("./cipher.txt", encrypted_text).unwrap();
}

fn encrypt(plain_text: u8, key1: u8, key2: u8) -> u8 {
    let after_ip = initial_permutation(plain_text);
    let after_fx = fx(key1, after_ip);
    let after_part1 = swap_8bit(after_fx);
    let after_fx = fx(key2, after_part1);
    let result = reverse_initial_permutation(after_fx);
    result
}

fn fx(key: u8, input: u8) -> u8 {
    let [left_ip, right_ip] = split_8bit(input);

    let after_ep = expanded_permutation(right_ip);

    let after_ep_xor_key = key ^ after_ep;
    let [left_ep, right_ep] = split_8bit(after_ep_xor_key);

    let left_sbox = sbox_left(left_ep);
    let right_sbox = sbox_right(right_ep);
    let after_sbox = left_sbox << 2 | right_sbox;

    let after_p4 = p4_permutation(after_sbox);

    let after_p4_xor = after_p4 ^ left_ip;
    let result = (after_p4_xor << 4) | right_ip;

    return result;
}

fn swap_8bit(data: u8) -> u8 {
    return (data >> 4) | ((data << 4) & 0b11110000);
}

fn initial_permutation(data: u8) -> u8 {
    let bit8 = is_true_bit(data as u16, 0) as u8;
    let bit7 = is_true_bit(data as u16, 1) as u8;
    let bit6 = is_true_bit(data as u16, 2) as u8;
    let bit5 = is_true_bit(data as u16, 3) as u8;
    let bit4 = is_true_bit(data as u16, 4) as u8;
    let bit3 = is_true_bit(data as u16, 5) as u8;
    let bit2 = is_true_bit(data as u16, 6) as u8;
    let bit1 = is_true_bit(data as u16, 7) as u8;

    return (bit7)
        | bit5 << 1
        | bit8 << 2
        | bit4 << 3
        | bit1 << 4
        | bit3 << 5
        | bit6 << 6
        | bit2 << 7;
}

fn reverse_initial_permutation(data: u8) -> u8 {
    let bit8 = is_true_bit(data as u16, 0) as u8;
    let bit7 = is_true_bit(data as u16, 1) as u8;
    let bit6 = is_true_bit(data as u16, 2) as u8;
    let bit5 = is_true_bit(data as u16, 3) as u8;
    let bit4 = is_true_bit(data as u16, 4) as u8;
    let bit3 = is_true_bit(data as u16, 5) as u8;
    let bit2 = is_true_bit(data as u16, 6) as u8;
    let bit1 = is_true_bit(data as u16, 7) as u8;

    return (bit6)
        | bit8 << 1
        | bit2 << 2
        | bit7 << 3
        | bit5 << 4
        | bit3 << 5
        | bit1 << 6
        | bit4 << 7;
}

fn expanded_permutation(data: u8) -> u8 {
    let bit4 = is_true_bit(data as u16, 0) as u8;
    let bit3 = is_true_bit(data as u16, 1) as u8;
    let bit2 = is_true_bit(data as u16, 2) as u8;
    let bit1 = is_true_bit(data as u16, 3) as u8;

    return (bit1)
        | bit4 << 1
        | bit3 << 2
        | bit2 << 3
        | bit3 << 4
        | bit2 << 5
        | bit1 << 6
        | bit4 << 7;
}

fn sbox_left(data: u8) -> u8 {
    let sbox0 = [[1, 0, 3, 2], [3, 2, 1, 0], [0, 2, 1, 3], [3, 1, 3, 2]];
    let row = ((data & (1 << 3)) >> 2) | (data & 1);
    let column = ((data & (1 << 2)) >> 1) | ((data & (1 << 1)) >> 1);
    return sbox0[row as usize][column as usize];
}

fn sbox_right(data: u8) -> u8 {
    let sbox1 = [[0, 1, 2, 3], [2, 0, 1, 3], [3, 0, 1, 0], [2, 1, 0, 3]];
    let row = ((data & (1 << 3)) >> 2) | (data & 1);
    let column = ((data & (1 << 2)) >> 1) | ((data & (1 << 1)) >> 1);
    return sbox1[row as usize][column as usize];
}

fn p4_permutation(data: u8) -> u8 {
    let bit_4 = is_true_bit(data as u16, 0) as u8;
    let bit_3 = is_true_bit(data as u16, 1) as u8;
    let bit_2 = is_true_bit(data as u16, 2) as u8;
    let bit_1 = is_true_bit(data as u16, 3) as u8;

    return (bit_1) | bit_3 << 1 | bit_4 << 2 | bit_2 << 3;
}

fn split_8bit(data: u8) -> [u8; 2] {
    let left = data >> 4;
    let right = data & 0b00001111;
    [left, right]
}

fn is_true_bit(key: u16, bit: u8) -> bool {
    (key & 1 << bit) != 0
}

コード全文は以下にプッシュしています。

https://github.com/diggymo/s-des-on-rust

実行結果

バージョン情報は以下の通りです。また、暗号利用モードは最も簡単なECBモード(全てのブロックで同じ鍵を利用)で実装しています。

  • cargo 1.74.0 (ecb9851af 2023-10-18)
  • rustup 1.26.0 (5af9b9484 2023-04-05)
  • edition = "2021"

以下のテキストファイルを暗号化します。

plain.txt
1234567890
hogehoge
私の名前はmorimorikochanです
Diggy-mo!!!

cargo run実行後、暗号化された内容がencrypted.txtとして出力されました。
この内容を見ただけでは元の文章を推測できません。

スクリーンショット 2024-09-24 13.44.08
encrypted.txt

また、このencrypted.txtを復号したdecrypt.txtも同時に出力されています。
以下のように、もとのファイルと完全に一致していることがわかりました。

decrypted.txt
1234567890
hogehoge
私の名前はmorimorikochanです
Diggy-mo!!!

まとめ・所感

  • S-DESは、DESの仕様を簡略化したブロック暗号であることがわかりました
  • RustでS-DESの暗号化を実装できました
    • 追加ライブラリがなくても十分実装できる内容であることがわかりました
    • bit列を入れ替える実装が少し長いように感じました
    • 今回はテストデータ(入力と出力)があったので実装を迷うことがなかったが、もしテストデータがなかったら完成まで辿り着けなかった可能性が高いと思いました
    • 暗号化の実装ができてしまえば復号や鍵の生成処理の実装は比較的容易にできることがわかりました
  • 既存のS-DESの処理フローを説明した資料では、bit数について記載されているものがなかったので、その面ではとてもわかりやすくなっていると思います。
  • 次回機会があれば暗号利用モードをECB以外で実装したいと思います💪

参考資料

Share this article

facebook logohatena logotwitter logo

© Classmethod, Inc. All rights reserved.